// @author U095159L VARUN GANESH
// all functions in this file  are implemented by the author unless specifically indicated
function a_star(current_position, destination, grid, columns, rows, allow_diagonals)
{
    //Create current_position and player_position as true nodes
    current_position = new node(current_position[0], current_position[1], -1, -1, -1, -1);
    destination = new node(destination[0], destination[1], -1, -1, -1, -1);

    var open = []; //List of open nodes (nodes to be inspected)
    var closed = []; //List of closed nodes (nodes we've already inspected)

    var g = 0; //Cost from current_position to current node
    var h = heuristic(current_position, destination); //Cost from current node to player_position
    var f = g+h; //Cost from current_position to player_position going through the current node

    //Push the current_position node onto the list of open nodes
    open.push(current_position);

    if(current_position.x < 0 || current_position.x >= columns || current_position.y < 0 || current_position.y >= rows){
        return [];
    }
    else if(destination.x < 0 || destination.x >= columns || destination.y < 0 || destination.y >= rows){
        return[];
    }
    else{
        //Keep going while there's nodes in our open list
        while (open.length > 0)
        {
            //Find the best open node (lowest f value)

            //Alternately, you could simply keep the open list sorted by f value lowest to highest,
            //in which case you always use the first node
            var best_cost = open[0].f;
            var best_node = 0;

            for (var i = 1; i < open.length; i++)
            {
                if (open[i].f < best_cost)
                {
                    best_cost = open[i].f;
                    best_node = i;
                }
            }

            //Set it as our current node
            var current_node = open[best_node];

            //Check if we've reached our player_position
            if (current_node.x == destination.x && current_node.y == destination.y)
            {
                var path = [destination]; //Initialize the path with the player_position node

                //Go up the chain to recreate the path
                while (current_node.parent_index != -1)
                {
                    current_node = closed[current_node.parent_index];
                    path.unshift(current_node);
                }

                return path;
            }

            //Remove the current node from our open list
            open.splice(best_node, 1);

            //Push it onto the closed list
            closed.push(current_node);

            //Expand our current node (look in all 8 directions)
            for (var new_node_x = Math.max(0, current_node.x-1); new_node_x <= Math.min(columns-1, current_node.x+1); new_node_x++)
                for (var new_node_y = Math.max(0, current_node.y-1); new_node_y <= Math.min(rows-1, current_node.y+1); new_node_y++)
                {
                    if (!allow_diagonals)
                    {
                        if (new_node_x != current_node.x && new_node_y != current_node.y)
                            continue;
                    }

                    if (grid[new_node_y][new_node_x] == 0 //If the new node is open
                        || (destination.x == new_node_x && destination.y == new_node_y)) //or the new node is our player_position
                    {
                        //See if the node is already in our closed list. If so, skip it.
                        var found_in_closed = false;
                        for (var i in closed)
                            if (closed[i].x == new_node_x && closed[i].y == new_node_y)
                            {
                                found_in_closed = true;
                                break;
                            }

                        if (found_in_closed)
                            continue;

                        //See if the node is in our open list. If not, use it.
                        var found_in_open = false;
                        for (var i in open)
                            if (open[i].x == new_node_x && open[i].y == new_node_y)
                            {
                                found_in_open = true;
                                break;
                            }

                        if (!found_in_open)
                        {
                            var new_node = new node(new_node_x, new_node_y, closed.length-1, -1, -1, -1);

                            new_node.g = current_node.g + Math.floor(Math.sqrt(Math.pow(new_node.x-current_node.x, 2)+Math.pow(new_node.y-current_node.y, 2)));
                            new_node.h = heuristic(new_node, destination);
                            new_node.f = new_node.g+new_node.h;

                            open.push(new_node);
                        }
                    }
                }
        }
        return [];
    }

    return [];
}

//An A* heurisitic must be admissible, meaning it must never overestimate the distance to the goal.
//In other words, it must either underestimate or return exactly the distance to the goal.
function heuristic(current_node, player_position)
{
    //Find the straight-line distance between the current node and the player_position. (Thanks to id for the improvement)
    //return Math.floor(Math.sqrt(Math.pow(current_node.x-player_position.x, 2)+Math.pow(current_node.y-player_position.y, 2)));
    var x = current_node.x-player_position.x;
    var y = current_node.y-player_position.y;
    return x*x+y*y;
}


/* Each node will have six values:
 X position
 Y position
 Index of the node's parent in the closed array
 Cost from current_position to current node
 Heuristic cost from current node to player_position
 Cost from current_position to player_position going through the current node
 */

function node(x, y, parent_index, g, h, f)
{
    this.x = x;
    this.y = y;
    this.parent_index = parent_index;
    this.g = g;
    this.h = h;
    this.f = f;
}